public class Rob1 {
    // 打家劫舍1
    // https://www.nowcoder.com/practice/c5fbf7325fbd4c0ea3d0c3ea6bc6cc79?tpId=295&tqId=2285793&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    public int rob (int[] nums) {
        // write code here
        int len = nums.length;
        // 状态表示
        // f[i]表示第i个房子偷时候的最大金额
        int[] f = new int[len+1];
        // g[i]表示第i个房子不偷时候的最大金额
        int[] g = new int[len+1];
        // 状态转移方程
        // f[i] = max(max(f[i-2], g[i-2]), g[i-1]) + nums[i]
        // g[i] = max(max(f[i-1], g[i-1]), f[i-2]);
        f[1] = nums[0];
        for (int i = 2; i <= len; i++) {
            f[i] = Math.max(Math.max(f[i-2], g[i-2]), g[i-1]) + nums[i-1];
            g[i] = Math.max(Math.max(f[i-1], g[i-1]), f[i-2]);
        }
        return Math.max(f[len], g[len]);
    }
}
